package com.cat.greedyAlgorithm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-deletions-to-make-character-frequencies-unique/description/
 * @create 2025/8/21 17:00
 * @since JDK17
 */

public class Solution11 {
    public int minDeletions(String s) {
        int[] h = new int[26];
        int n = s.length(), ans = 0;
        for (int i = 0; i < n; i++) {
            h[s.charAt(i) - 'a']++;
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            if (h[i] != 0) {
                list.add(h[i]);
            }
        }
        Collections.sort(list);
        n = list.size();
        int cnt = list.get(n - 1);
        for (int i = n - 2; i >= 0; i--) {  //
            if (list.get(i) >= cnt) {
                ans += list.get(i) + 1 - cnt;
                cnt -= list.get(i) + 1 - cnt;
            } else {
                cnt = list.get(i);
            }
        }

        return ans;
    }
}
